package com.javabasic.algorithm.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [748. Shortest Completing Word](https://leetcode-cn.com/problems/shortest-completing-word/)
 * @since Created by work on 2021/12/10 10:39 下午
 */
public class ShortestCompletingWord {

    final int LETTER_SIZE = 26;

    /**
     * 暴力解法
     * @param licensePlate
     * @param words
     * @return
     */
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int len = words.length;
        int licenseLen = licensePlate.length(), num, index;
        HashMap<Integer, Integer> letterToNum = new HashMap<>(LETTER_SIZE);
        char charAt;
        for (int i = 0; i < licenseLen; i++) {
            charAt = licensePlate.charAt(i);
            if (charAt >= 'a' && charAt <= 'z') {
                index = charAt-'a';
                num = letterToNum.getOrDefault(index,0);
                num++;
                letterToNum.put(index,num);
            } else if (charAt >= 'A' && charAt <= 'Z') {
                index = charAt-'A';
                num = letterToNum.getOrDefault(index,0);
                num++;
                letterToNum.put(index,num);
            }
        }

        /**
         * 匿名内部类实现自定义排序
         */
        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() > o2.length()) return 1;
                if (o1.length() < o2.length()) return -1;
                return 0;
            }
        });

        /**
         * lambad式实现自定义排序
         */
        Arrays.sort(words, (pre,post) -> {
            if (pre.length() > post.length()) return 1;
            if (pre.length() < post.length()) return -1;
            return 0;
        });

        for (int i = 0; i < len; i++) {
            if (containAllLetter(words[i],letterToNum)) {
                return words[i];
            }
        }
        return null;
    }

    private boolean containAllLetter(String word, HashMap<Integer, Integer> letterToNum) {
        int len = word.length();

        int[] arr = new int[LETTER_SIZE];
        for (int i = 0; i < len; i++) {
            arr[word.charAt(i)-'a']++;
        }
        for (Map.Entry<Integer, Integer> entry : letterToNum.entrySet()) {
            if (arr[entry.getKey()] < entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}
